#include <vector>
#include <queue>
#include <iostream>
#include <unordered_set>
#include "TreeNode.hpp"
#include <algorithm>
#include <string>


#ifndef BACKTRACKING_H
#define BACKTRACKING_H

class BackTracking
{
public:
    BackTracking();
    ~BackTracking() = default;
    // 构建二叉树
    TreeNode* CreatTree(const std::vector<int>& nums,int i);
    // 释放二叉树
    void freeTree(TreeNode* root);
    // 层序遍历二叉树并打印
    void printTree(TreeNode* root);
    // 前序遍历,遇到值为7的节点就将值打印出来
    void preOrderWith7(TreeNode* root);
    // 前序遍历，遇到值为7的节点就储存根节点到该节点的节点路径
    void preOrderWith7path(TreeNode* root,std::vector<int>& path,std::vector<std::vector<int>>& res);
    // 前序遍历，遇到值为7的节点就储存根节点到该节点的节点路径,剪枝值为3的路径
    void preOrderWith7pathNo3(TreeNode* root,std::vector<int>& path,std::vector<std::vector<int>>& res);

    // 回溯算法解决全排列问题,无相等元素的情况
    void backtrackingforPermutationsI(std::vector<int> &state,const std::vector<int>& choices,
                                     std::vector<bool>& selected,std::vector<std::vector<int>> &res);
    // 回溯算法解决全排列问题,无相等元素的情况
    void backtrackingforPermutationsII(std::vector<int> &state,const std::vector<int>& choices,
                                     std::vector<bool>& selected,std::vector<std::vector<int>> &res);

    // 回溯算法解决子集和问题，选择集中无重复元素，包含重复子集的解法
    void backtrackingforSubSetSumINaive(std::vector<int> &state,const std::vector<int>& choices,
                                        int total,int target,std::vector<std::vector<int>> &res);
    // 回溯算法解决子集和问题，选择集中无重复元素，无重复子集的解法
    void backtrackingforSubSetSumI(std::vector<int> &state,const std::vector<int>& choices,
                                        int target,int start,std::vector<std::vector<int>> &res);
    // 回溯算法解决子集和问题，选择集中存在重复元素，无重复子集的解法
    void backtrackingforSubSetSumII(std::vector<int> &state,const std::vector<int>& choices,
                                        int target,int start,std::vector<std::vector<int>> &res);

    // 回溯算法解决N皇后问题
    void backtrackingfornQueens(int row,int n,std::vector<std::vector<std::string>> &state,std::vector<bool>& cols,
                                std::vector<bool>& diags1,std::vector<bool>& diags2,
                                std::vector<std::vector<std::vector<std::string>>>& res);
private:
    
};

#endif